package leetcode;

/**
 * 给定不同面额的硬币 coins 和一个总金额
 * amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
 * 
 * @author maodou38
 *
 */
class Solution322_leetcode_memorysearch {//记忆化搜索
	int[] memo;

	public int coinChange(int[] coins, int amount) {
		if (coins.length == 0) {
			return -1;
		}
		memo = new int[amount];

		return findWay(coins, amount);
	}

	// memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为-1
	// findWay函数的目的是为了找到 amount数量的零钱可以兑换的最少硬币数量，返回其值int
	public int findWay(int[] coins, int amount) {
		if (amount < 0) {
			return -1;
		}
		if (amount == 0) {
			return 0;
		}
		// 记忆化的处理，memo[n]用赋予了值，就不用继续下面的循环
		// 直接的返回memo[n] 的最优值
		if (memo[amount - 1] != 0) {
			return memo[amount - 1];
		}
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < coins.length; i++) {
			int res = findWay(coins, amount - coins[i]);
			if (res >= 0 && res < min) {
				min = res + 1; // 加1，是为了加上得到res结果的那个步骤中，兑换的一个硬币
			}
		}
		memo[amount - 1] = (min == Integer.MAX_VALUE ? -1 : min);
		return memo[amount - 1];
	}
}
